COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00009 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A75.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, December 6, 1988}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf The Post Correspondence Problem}

Let $a↓i$ and $b↓i$ $(1 \leq i \leq m)$ be strings.  
Let the mapping $\alpha$ map the sequence $I = \langle i↓1, i↓2,\dots, 
i↓n\rangle$ into the string
$a↓{i↓1} a↓{i↓2}\dots a↓{i↓n}$, and $\beta$ map $I$ into $b↓{i↓1} b↓{i↓2}
\dots b↓{i↓n}$.  The Post correspondence problem for $\alpha$ and $\beta$ is
whether there is a nonempty sequence $I$ for which $I\alpha = I\beta$.  If
$I = J \otimes K$, $J\alpha K\alpha = I\alpha = I\beta = J\beta K\beta$.
Then $J\alpha$ and $J\beta$ must be equal, or one must be a 
prefix of the other, say $J\alpha = J\beta x$; we call $x$ the 
{\it overhang} of $J$.

Let $S = \{\langle a↓i, b↓i\rangle\}$ be a finite set of productions
(pairs of strings in $\Sigma↑*$).  Define relation $\Rightarrow \hbox {as}\, 
\{\langle xay, xby\rangle \mid x, y\in\Sigma↑*, 
\langle a,b\rangle\in S\}.$ 
For given $S$, the {\it word problem} of $S$ is the question $W(u,v) ≡ u \aRa v$:
can $u$ be changed into $v$ using the productions in $S$?  If $x$ is the
string $abc$, let $\la{x} =\, \diamond a\diamond b\diamond c$, $\ra{x} = 
a\diamond b\diamond
c\diamond$, $\da{x} =\, \diamond a\diamond b\diamond c\diamond$.

From any word problem $W(u,v)$, we can construct a Post correspondence
problem consisting of these pairs:
$$
\halign{\qquad$#$\hfil\qquad&$#$\hfil\qquad&$#$\hfil\qquad&#\hfil\cr
(1) & \vdash\diamond\ra{u}\mid&\vdash\diamond\cr
(2↓s)&\diamond s&s\diamond&for each $s\in\Sigma$\cr
(3↓i)&\la{b}↓i&\ra{a}↓i&for each $(a↓i \rightarrow b↓i) \in S$\cr
(4)&\diamond\mid&\mid\diamond\cr
(5)&\diamond\dashv&\mid\la{v}\diamond\dashv\cr}
$$
If $u = w↓0\Rightarrow w↓1\Rightarrow\ldots\Rightarrow w↓n = v$,
there is a solution $I$ of the PCP, for which
$$I\alpha = I\beta =\, \vdash \da{w}↓0\mid\da{w}↓1\mid\ldots\mid\da{w}↓n\dashv.$$

Successive segments of $I$ are shown below with the overhangs by which
$I↓\alpha$ exceeds $I↓\beta$
$$
\halign{\qquad$#$\hfil \qquad&\hfil$#$&$#$\hfil\cr
(1) &\ra{u}\mid\null = \ra{w}↓0\mid\null = \ra{x}↓0\ra{a}↓1\ra{y}↓0&\null\mid\cr
(2↓{\it various})&\ra{a}↓1\ra{y}↓0&\null\mid\la{x}↓0\cr
(3↓1)&\ra{y}↓0&\null\mid\la{x}↓0\la{b}↓1\cr
(2↓{\it various})&&\null\mid\la{x}↓0\la{b}↓1\la{y}↓0 = \null\mid\la{w}↓1\cr
(4)&\ra{w}↓1\mid\hfill\cr}
$$
By $n$ repetitions of the pattern 2* 3 2* 4, leaving off the last 4, we get to
an overhang of $\mid\la{w}↓n =\, \mid \la{v}$.  Use of pair 5 leaves an empty
overhang, at which point $I$ is a solution.  Therefore, if the word problem
has a solution, so does the PCP.

In the other direction, suppose that $I$ is a solution of the PCP.  $I$ must
begin with 1, yielding an overhang of $I\alpha$ beyond $I\beta$ that
includes a single $\mid$, so is nonempty.  This situation continues until
$I$ contains 5, at which point $I\alpha$ and $I\beta$ each contain a single
$\dashv$, at the right end, so $I$ is a solution.  By induction on the
length of $I$, the overhang after
1 and before 5 is of the form $\ra{p}\mid\la{q}$ where $u \aRa qp$.  For
example: 4 can be used only if $p$ is empty, changing overhang
$\mid \la{q}$ where $u \aRa q = q\Lambda$ to $\ra{q}\mid$ where $u \aRa q = 
\Lambda q$.  Another example: $3↓i$ only can be used if $\ra{p} = 
\ra{a}↓i \ra{r}$, changing
overhang $\ra{a}↓i \ra{r}\mid\la{q}$ to $\ra{r}\mid
\la{q}\la{b}↓i$.  Using the induction hypothesis, $u \aRa qa↓i r \Rightarrow
q b↓i r$, and the invariant is preserved.

When 5 is finally used, the overhang must be $\mid \la{v}$, so by the induction
hypothesis, $u \aRa v\Lambda = v$, solving the word problem.  If the
PCP has a solution, so does the word problem.
\bye